import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class MainDP41 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
         int n = scan.nextInt() ;
         int v = scan.nextInt() ;
         int[] vArr = new int[n+1];
         int[] sArr = new int[n+1] ; 
         for(int i=1 ; i <= n ; i  ++){
            vArr[i] = scan.nextInt() ;
            sArr[i] = scan.nextInt() ; 
         }
         int[][] dp = new int[n+1][v+1] ;  
         for(int i=1 ; i<= n ; i ++){
            for(int j=1 ; j<= v ; j  ++){
                dp[i][j] = dp[i-1][j] ; 
                if(j >= vArr[i]){
                    dp[i][j] = Math.max(sArr[i]+dp[i-1][j-vArr[i]] , dp[i][j]);
                }
            }
         }
        System.out.println(dp[n][v]);
         dp = new int[n+1][v+1] ;
         for(int i=1 ; i<=v; i ++) dp[0][i] = -1 ;
         for(int i=1 ; i<= n ; i ++){
            for(int j=1 ; j<=v ; j ++){
               dp[i][j] = dp[i-1][j] ; 
               if(j>=vArr[i] && dp[i-1][j-vArr[i]] != -1){
                  dp[i][j] = Math.max(dp[i][j] , sArr[i]+dp[i-1][j-vArr[i]]);
               }
            }
         }
       System.out.println(dp[n][v]==-1?0:dp[n][v]);
    
    }
}